package com.second.app.algorithm;

import java.util.Arrays;

public class QuickSortD {

    public static void main(String[] args) {

//        int[] arr = {1, 12, 5, 18, 10, 3, 2, 9};
//        quickSort(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(arr));


        int[] arr1 = {7, 12, 5, 18, 10, 3, 2, 9};
        quickSort1(arr1, 0, arr1.length - 1);
        System.out.println(Arrays.toString(arr1));
    }


    public static void quickSort1(int[] arr, int left, int right) {

        if (left >= right) {
            return;
        }

        int pivolt = arr[left];

        int i = left, j = right;

        while (i < j) {

            // 从右往左找
            while (i < j && arr[j] >= pivolt) {
                j--;
            }
            arr[i] = arr[j];
            // 从左往右找
            while (i < j && arr[i] <= pivolt) {
                i++;
            }
            arr[j] = arr[i];

        }
        arr[i] = pivolt;
        quickSort1(arr, left, i - 1);
        quickSort1(arr, i + 1, right);

    }


    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, 0, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        // 选最后一个索引位置的元素作为 基准pivot=2
        int pivot = arr[high];
        // i=-1
        int i = low - 1;
        //{12, 5, 18, 10, 3, 2}
        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}
